using System;
using System.Diagnostics;
using Community.CsharpSqlite.Entity;

namespace Community.CsharpSqlite
{
    public partial class Sqlite3
    {
        /*
    ** 2008 February 16
    **
    ** The author disclaims copyright to this source code.  In place of
    ** a legal notice, here is a blessing:
    **
    **    May you do good and not evil.
    **    May you find forgiveness for yourself and forgive others.
    **    May you share freely, never taking more than you give.
    **
    *************************************************************************
    ** This file implements an object that represents a fixed-length
    ** bitmap.  Bits are numbered starting with 1.
    **
    ** A bitmap is used to record which pages of a database file have been
    ** journalled during a transaction, or which pages have the "dont-write"
    ** property.  Usually only a few pages are meet either condition.
    ** So the bitmap is usually sparse and has low cardinality.
    ** But sometimes (for example when during a DROP of a large table) most
    ** or all of the pages in a database can get journalled.  In those cases,
    ** the bitmap becomes dense with high cardinality.  The algorithm needs
    ** to handle both cases well.
    **
    ** The size of the bitmap is fixed when the object is created.
    **
    ** All bits are clear when the bitmap is created.  Individual bits
    ** may be set or cleared one at a time.
    **
    ** Test operations are about 100 times more common that set operations.
    ** Clear operations are exceedingly rare.  There are usually between
    ** 5 and 500 set operations per Bitvec object, though the number of sets can
    ** sometimes grow into tens of thousands or larger.  The size of the
    ** Bitvec object is the number of pages in the database file at the
    ** start of a transaction, and is thus usually less than a few thousand,
    ** but can be as large as 2 billion for a really big database.
    *************************************************************************
    **  Included in SQLite3 port to C#-SQLite;  2008 Noah B Hart
    **  C#-SQLite is an independent reimplementation of the SQLite software library
    **
    **  SQLITE_SOURCE_ID: 2009-12-07 16:39:13 1ed88e9d01e9eda5cbc622e7614277f29bcc551c
    **
    **  $Header: Community.CsharpSqlite/src/bitvec_c.cs,v bcbd36f24b23 2010/02/18 17:35:24 Noah $
    *************************************************************************
    */
        //#include "sqliteInt.h"


        /*
    ** Create a new bitmap object able to handle bits between 0 and iSize,
    ** inclusive.  Return a pointer to the new object.  Return NULL if
    ** malloc fails.
    */

        private static Bitvec sqlite3BitvecCreate(uint iSize)
        {
            Bitvec p;
            //Debug.Assert( sizeof(p)==BITVEC_SZ );
            p = new Bitvec(); //Malloc.MallocZero( sizeof(p) );
            if (p != null)
            {
                p.iSize = iSize;
            }
            return p;
        }

        /*
    ** Check to see if the i-th bit is set.  Return true or false.
    ** If p is NULL (if the bitmap has not been created) or if
    ** i is out of range, then return false.
    */

        private static int sqlite3BitvecTest(Bitvec p, uint i)
        {
            if (p == null || i == 0) return 0;
            if (i > p.iSize) return 0;
            i--;
            while (p.iDivisor != 0)
            {
                uint bin = i/p.iDivisor;
                i = i%p.iDivisor;
                p = p.u.apSub[bin];
                if (null == p)
                {
                    return 0;
                }
            }
            if (p.iSize <= Const.BITVEC_NBIT)
            {
                return ((p.u.aBitmap[i/Const.BITVEC_SZELEM] & (1 << (int) (i & (Const.BITVEC_SZELEM - 1)))) != 0)
                           ? 1
                           : 0;
            }
            else
            {
                uint h = Const.BITVEC_HASH(i++);
                while (p.u.aHash[h] != 0)
                {
                    if (p.u.aHash[h] == i) return 1;
                    h = (h + 1)%Const.BITVEC_NINT;
                }
                return 0;
            }
        }

        /*
    ** Set the i-th bit.  Return 0 on success and an error code if
    ** anything goes wrong.
    **
    ** This routine might cause sub-bitmaps to be allocated.  Failing
    ** to get the memory needed to hold the sub-bitmap is the only
    ** that can go wrong with an insert, assuming p and i are valid.
    **
    ** The calling function must ensure that p is a valid Bitvec object
    ** and that the value for "i" is within range of the Bitvec object.
    ** Otherwise the behavior is undefined.
    */

        private static int sqlite3BitvecSet(Bitvec p, uint i)
        {
            uint h;
            if (p == null) return StatusCode.SQLITE_OK;
            Debug.Assert(i > 0);
            Debug.Assert(i <= p.iSize);
            i--;
            while ((p.iSize > Const.BITVEC_NBIT) && p.iDivisor != 0)
            {
                uint bin = i/p.iDivisor;
                i = i%p.iDivisor;
                if (p.u.apSub[bin] == null)
                {
                    p.u.apSub[bin] = sqlite3BitvecCreate(p.iDivisor);
                    if (p.u.apSub[bin] == null) return StatusCode.SQLITE_NOMEM;
                }
                p = p.u.apSub[bin];
            }
            if (p.iSize <= Const.BITVEC_NBIT)
            {
                p.u.aBitmap[i/Const.BITVEC_SZELEM] |= (byte) (1 << (int) (i & (Const.BITVEC_SZELEM - 1)));
                return StatusCode.SQLITE_OK;
            }
            h = Const.BITVEC_HASH(i++);
            /* if there wasn't a hash collision, and this doesn't */
            /* completely fill the hash, then just add it without */
            /* worring about sub-dividing and re-hashing. */
            if (0 == p.u.aHash[h])
            {
                if (p.nSet < (Const.BITVEC_NINT - 1))
                {
                    goto bitvec_set_end;
                }
                else
                {
                    goto bitvec_set_rehash;
                }
            }
            /* there was a collision, check to see if it's already */
            /* in hash, if not, try to find a spot for it */
            do
            {
                if (p.u.aHash[h] == i) return StatusCode.SQLITE_OK;
                h++;
                if (h >= Const.BITVEC_NINT) h = 0;
            } while (p.u.aHash[h] != 0);
            /* we didn't find it in the hash.  h points to the first */
            /* available free spot. check to see if this is going to */
            /* make our hash too "full".  */
            bitvec_set_rehash:
            if (p.nSet >= Const.BITVEC_MXHASH)
            {
                uint j;
                int rc;
                var aiValues = new uint[Const.BITVEC_NINT]; // = sqlite3StackAllocRaw(0, sizeof(p->u.aHash));
                if (aiValues == null)
                {
                    return StatusCode.SQLITE_NOMEM;
                }
                else
                {
                    Buffer.BlockCopy(p.u.aHash, 0, aiValues, 0, aiValues.Length*(sizeof (uint)));
                        // memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));
                    p.u.apSub = new Bitvec[Const.BITVEC_NPTR]; //memset(p->u.apSub, 0, sizeof(p->u.apSub));
                    p.iDivisor = (uint) ((p.iSize + Const.BITVEC_NPTR - 1)/Const.BITVEC_NPTR);
                    rc = sqlite3BitvecSet(p, i);
                    for (j = 0; j < Const.BITVEC_NINT; j++)
                    {
                        if (aiValues[j] != 0) rc |= sqlite3BitvecSet(p, aiValues[j]);
                    }
                    //sqlite3StackFree( null, aiValues );
                    return rc;
                }
            }
            bitvec_set_end:
            p.nSet++;
            p.u.aHash[h] = i;
            return StatusCode.SQLITE_OK;
        }

        /*
    ** Clear the i-th bit.
    **
    ** pBuf must be a pointer to at least BITVEC_SZ bytes of temporary storage
    ** that BitvecClear can use to rebuilt its hash table.
    */

        private static void sqlite3BitvecClear(Bitvec p, uint i, uint[] pBuf)
        {
            if (p == null) return;
            Debug.Assert(i > 0);
            i--;
            while (p.iDivisor != 0)
            {
                uint bin = i/p.iDivisor;
                i = i%p.iDivisor;
                p = p.u.apSub[bin];
                if (null == p)
                {
                    return;
                }
            }
            if (p.iSize <= Const.BITVEC_NBIT)
            {
                p.u.aBitmap[i/Const.BITVEC_SZELEM] &= (byte) ~((1 << (int) (i & (Const.BITVEC_SZELEM - 1))));
            }
            else
            {
                uint j;
                uint[] aiValues = pBuf;
                Array.Copy(p.u.aHash, aiValues, p.u.aHash.Length); //memcpy(aiValues, p->u.aHash, sizeof(p->u.aHash));
                p.u.aHash = new uint[aiValues.Length]; // memset(p->u.aHash, 0, sizeof(p->u.aHash));
                p.nSet = 0;
                for (j = 0; j < Const.BITVEC_NINT; j++)
                {
                    if (aiValues[j] != 0 && aiValues[j] != (i + 1))
                    {
                        uint h = Const.BITVEC_HASH(aiValues[j] - 1);
                        p.nSet++;
                        while (p.u.aHash[h] != 0)
                        {
                            h++;
                            if (h >= Const.BITVEC_NINT) h = 0;
                        }
                        p.u.aHash[h] = aiValues[j];
                    }
                }
            }
        }

        /*
    ** Destroy a bitmap object.  Reclaim all memory used.
    */

        private static void sqlite3BitvecDestroy(ref Bitvec p)
        {
            if (p == null) return;
            if (p.iDivisor != 0)
            {
                uint i;
                for (i = 0; i < Const.BITVEC_NPTR; i++)
                {
                    sqlite3BitvecDestroy(ref p.u.apSub[i]);
                }
            }
            //Malloc.sqlite3_free( ref p );
        }

        /*
    ** Return the value of the iSize parameter specified when Bitvec *p
    ** was created.
    */

        private static uint sqlite3BitvecSize(Bitvec p)
        {
            return p.iSize;
        }

#if !SQLITE_OMIT_BUILTIN_TEST
        /*
** Let V[] be an array of unsigned characters sufficient to hold
** up to N bits.  Let I be an integer between 0 and N.  0<=I<N.
** Then the following macros can be used to set, clear, or test
** individual bits within V.
*/
        //#define SETBIT(V,I)      V[I>>3] |= (1<<(I&7))
        private static void SETBIT(byte[] V, int I)
        {
            V[I >> 3] |= (byte) (1 << (I & 7));
        }

        //#define CLEARBIT(V,I)    V[I>>3] &= ~(1<<(I&7))
        private static void CLEARBIT(byte[] V, int I)
        {
            V[I >> 3] &= (byte) ~(1 << (I & 7));
        }

        //#define TESTBIT(V,I)     (V[I>>3]&(1<<(I&7)))!=0
        private static int TESTBIT(byte[] V, int I)
        {
            return (V[I >> 3] & (1 << (I & 7))) != 0 ? 1 : 0;
        }

        /*
    ** This routine runs an extensive test of the Bitvec code.
    **
    ** The input is an array of integers that acts as a program
    ** to test the Bitvec.  The integers are opcodes followed
    ** by 0, 1, or 3 operands, depending on the opcode.  Another
    ** opcode follows immediately after the last operand.
    **
    ** There are 6 opcodes numbered from 0 through 5.  0 is the
    ** "halt" opcode and causes the test to end.
    **
    **    0          Halt and return the number of errors
    **    1 N S X    Set N bits beginning with S and incrementing by X
    **    2 N S X    Clear N bits beginning with S and incrementing by X
    **    3 N        Set N randomly chosen bits
    **    4 N        Clear N randomly chosen bits
    **    5 N S X    Set N bits from S increment X in array only, not in bitvec
    **
    ** The opcodes 1 through 4 perform set and clear operations are performed
    ** on both a Bitvec object and on a linear array of bits obtained from malloc.
    ** Opcode 5 works on the linear array only, not on the Bitvec.
    ** Opcode 5 is used to deliberately induce a fault in order to
    ** confirm that error detection works.
    **
    ** At the conclusion of the test the linear array is compared
    ** against the Bitvec object.  If there are any differences,
    ** an error is returned.  If they are the same, zero is returned.
    **
    ** If a memory allocation error occurs, return -1.
    */

        private static int sqlite3BitvecBuiltinTest(uint sz, int[] aOp)
        {
            Bitvec pBitvec = null;
            byte[] pV = null;
            int rc = -1;
            int i, nx, pc, op;
            uint[] pTmpSpace;

            /* Allocate the Bitvec to be tested and a linear array of
      ** bits to act as the reference */
            pBitvec = sqlite3BitvecCreate(sz);
            pV = Malloc.sqlite3_malloc((int) (sz + 7)/8 + 1);
            pTmpSpace = new uint[Const.BITVEC_SZ]; // Malloc.sqlite3_malloc( BITVEC_SZ );
            if (pBitvec == null || pV == null || pTmpSpace == null) goto bitvec_end;
            Array.Clear(pV, 0, (int) (sz + 7)/8 + 1); // memset( pV, 0, ( sz + 7 ) / 8 + 1 );

            /* NULL pBitvec tests */
            sqlite3BitvecSet(null, 1);
            sqlite3BitvecClear(null, 1, pTmpSpace);

            /* Run the program */
            pc = 0;
            while ((op = aOp[pc]) != 0)
            {
                switch (op)
                {
                    case 1:
                    case 2:
                    case 5:
                        {
                            nx = 4;
                            i = aOp[pc + 2] - 1;
                            aOp[pc + 2] += aOp[pc + 3];
                            break;
                        }
                    case 3:
                    case 4:
                    default:
                        {
                            nx = 2;
                            long i64Temp = 0;
                            Random.Randomness(sizeof (long), ref i64Temp);
                            i = (int) i64Temp;
                            break;
                        }
                }
                if ((--aOp[pc + 1]) > 0) nx = 0;
                pc += nx;
                i = (int) ((i & 0x7fffffff)%sz);
                if ((op & 1) != 0)
                {
                    SETBIT(pV, (i + 1));
                    if (op != 5)
                    {
                        if (sqlite3BitvecSet(pBitvec, (uint) i + 1) != 0) goto bitvec_end;
                    }
                }
                else
                {
                    CLEARBIT(pV, (i + 1));
                    sqlite3BitvecClear(pBitvec, (uint) i + 1, pTmpSpace);
                }
            }

            /* Test to make sure the linear array exactly matches the
      ** Bitvec object.  Start with the assumption that they do
      ** match (rc==0).  Change rc to non-zero if a discrepancy
      ** is found.
      */
            rc = sqlite3BitvecTest(null, 0) + sqlite3BitvecTest(pBitvec, sz + 1)
                 + sqlite3BitvecTest(pBitvec, 0)
                 + (int) (sqlite3BitvecSize(pBitvec) - sz);
            for (i = 1; i <= sz; i++)
            {
                if ((TESTBIT(pV, i)) != sqlite3BitvecTest(pBitvec, (uint) i))
                {
                    rc = i;
                    break;
                }
            }

            /* Free allocated structure */
            bitvec_end:
            //Malloc.sqlite3_free( ref pTmpSpace );
            //Malloc.sqlite3_free( ref pV );
            sqlite3BitvecDestroy(ref pBitvec);
            return rc;
        }
#endif
        //* SQLITE_OMIT_BUILTIN_TEST */
    }
}